/**
 * 
 */
package array.passed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * @author xyyi
 *
 */
public class Anagrams {

	/**
	Q:

	Given an array of strings, return all groups of strings that are anagrams.

	Note: All inputs will be in lower-case.

	For example:

	Input:　　["tea","and","ate","eat","den"]

	Output:   ["tea","ate","eat"]

	Interface: vector<string>anagrams(vector<string>&strs);

	A:

	首先简单介绍一下Anagram（回文构词法）。Anagrams是指由颠倒字母顺序组成的单词，比如“dormitory”颠倒字母顺序会变成“dirty room”，“tea”会变成“eat”。

	回文构词法有一个特点：单词里的字母的种类和数目没有改变，只是改变了字母的排列顺序。



	由此我们可以想到，只要将几个单词按照字母顺序进行排序，就可以通过比较判断他们是否是anagrams。

	思路：用map<string, int>记录排序后的字符串以及首次出现的位置。

	1. 从strs的第一个元素开始遍历，首先对元素进行排序得到s；

	2. 在map里查找s；

	3. 若不存在，将s以及该元素的下标存入map<string ,int>；

	4. 若存在，首先将第一次出现s时的原始字符串存入结果res，即strs[map[s]]，并将map[s]设置为-1（防止下次再存），再将该字符串本身存入结果res；

	5. 重复以上1-4步，直到遍历结束。
	 */
	public ArrayList<String> anagrams(String[] strs) {
		ArrayList<String> result = new ArrayList<String>();
		if (strs == null || strs.length == 0)
			return result;
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for (int i = 0; i < strs.length; i++) {
			char[] chars = strs[i].toCharArray();
			Arrays.sort(chars);
			String sortedStr = String.valueOf(chars);
			if (!map.containsKey(sortedStr)) {
				map.put(sortedStr, i);
			} else {
				if (map.get(sortedStr) != -1) {
					result.add(strs[map.get(sortedStr)]);
					map.put(sortedStr, -1);
				}
				result.add(strs[i]);
			}
		}

		return result;
	}

	/**
	 * 
	 */
	public Anagrams() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
